The approaches described in this section are approaches that could be pursued, but not necessarily approaches that have been previously conceived or pursued. Therefore, unless otherwise indicated, it should not be assumed that any of the approaches described in this section qualify as prior art merely by virtue of their inclusion in this section.
When an Operating System (OS) initializes a process for execution, the OS assigns to the process a memory address space which begins at virtual address 0x0 and which may go up to the maximum memory address space that the particular OS can assign to a process. The memory address space assigned to a process is a virtual memory address space which, during the execution of the process, is mapped by the OS to physical memory address space. (The physical memory address space used by a process during the process' execution typically does not begin at physical address 0x0.) For example, the virtual memory address space of a process may be divided into virtual memory pages that are mapped by the OS to physical memory pages. When a process is executing (i.e. during the runtime of a process), the OS also maps virtual addresses used by the process to the corresponding physical addresses in the physical memory. For example, when a process requests to access data at a particular virtual memory address, the OS translates the particular virtual memory address to the physical address in physical memory where the requested data is located.
When a process starts up, the process typically includes in its virtual memory address space all the executable code of the process and all other data needed by the process. Examples of process data include, but are not limited to, heaps, stacks, and other permanent or temporary data structures. In addition, a process may provide one or more components for managing the virtual memory address space assigned thereto and for dynamically allocating virtual memory when needed (e.g., by making calls to a malloc( ) function that is included in a C runtime library).
One example of a process is a Java Virtual Machine (JVM). A JVM process would typically provide one or more threads that are operable to manage the virtual memory address space of the JVM, for example, garbage collectors and other memory management threads. In current JVM implementations, JVM processes are operable to use contiguous heaps. For example, when a JVM process starts, the JVM process would typically allocate an object heap as a range of contiguous virtual memory addresses, where the size of the range is a parameter that may be pre-configured by a user or set by the JVM process itself. As used herein, “heap” refers to a portion of virtual memory that is managed by the process associated therewith. “Object heap” refers to a heap that is operable to store objects, which are any entities that may be instantiated by a process.
Contiguous heaps are widely used in process implementations because they allow for offset-based indexing into side data structures, which are used to manage the heaps and any information stored therein. (As used herein, “side data structure” refers to a portion of virtual memory that stores metadata information about a heap.) For example, a JVM process may use one or more side data structures to facilitate traversals and garbage collection of the objects stored in a contiguous heap.
The use of contiguous heaps, however, has some disadvantages. One disadvantage is that once a process allocates a contiguous heap (usually at start-up), the process cannot thereafter dynamically increase or decrease the size of the heap. This disadvantage is serious because the process cannot utilize its virtual memory address space efficiently. For example, if a process allocates a contiguous heap that is too big, the process may run out of virtual memory when it attempts to allocate memory for non-heap data. If a process allocates a contiguous heap that is too small, the process may not have enough heap space for the heap data that it needs during execution. This disadvantage is exacerbated for processes (e.g. servers and JVMs) that may need to run for relatively long periods of time under uneven workloads.
To address this disadvantage of contiguous heaps, some process implementations may use chunked heaps. (As used herein, “chunked heap” refers to a heap that comprises a plurality of chunks, which chunks are not allocated in a contiguous range of virtual memory addresses.) For example, a process may allocate the chunks of a chunked heap only when heap space is needed, and may de-allocate any heap chunks that are no longer needed. In this way, a process may manage its virtual memory address space more efficiently and may adjust the use of virtual memory space to the process' current workload.
Because chunked heaps include multiple chunks, chunked heaps do not allow for efficient offset-based indexing into side data structures. For example, according to one approach for using side data structures with a chunked heap, a header is included in each chunk. Any information related to a chunk (e.g. the size of the chunk, the location of side data structures associated with the chunk, etc.) is stored in a chunk table that is pointed to by a pointer stored into the chunk header. The chunk table is an associated array that indexes the side data structures for all chunks in the chunked heap based on the base address of each chunk. Look-ups into the chunk table for a particular chunk involve using the pointer stored in the header of that particular chunk to locate the associated array. A look-up is performed by using the base address of a chunk as an index into the associated array, where the look-up returns a pointer to a virtual memory address at which a side data structure associated with that chunk begins.
The disadvantage of the above approach for utilizing side data structures with chunked heaps is that the approach uses at least one level of indirection in order to get from a chunk to a side data structure associated with that chunk. Using indirection to access a side data structure is relatively slow because it involves at least one, and possibly more, memory accessing operations. For example, in order to access a side data structure for a particular chunk, a process needs to perform multiple memory accessing operations to determine a pointer to the side data structure (e.g. at least one memory accessing operation to locate the chunk table, and at least one memory accessing operation to perform a look-up into the chunk table). Such memory accessing operations are expensive and tend to hinder the process' performance if they are performed often.
Each chunk in a chunked heap may be specialized for storing a particular type of information such as, for example, a particular type of objects. Thus, prior to performing operations on a specialized chunk, a process may need to determine the type of the chunk in order to locate the executable instructions for the operations that need to be performed on that chunk. Determining the type of a chunk, however, may involve one or more expensive memory accessing operations. For example, according to one approach the type of a chunk may be stored in the chunk header or in a chunk table pointed to by a pointer stored in the chunk header—either way, a process needs to perform at least one memory accessing operation to determine the type of the chunk. In addition, after determining the type of the chunk, the process may need to perform at least one branching operation in order to get to the executable instructions for the specific operations that need to be performed on chunks of that particular type. However, branching operations are also very expensive and tend to hinder the process' performance if they are performed often.
Based on the forgoing, there is a clear need for techniques that efficiently utilize chunked heaps and overcome the disadvantages of the approach for utilizing chunked heaps that is described above.